package com.xyj.week01;

/**
 * 链表的归并排序
 */
public class T5 {


    public static void main(String[] args) {
        //初始化环形链表
        Node node = new Node(5);
        Node node1 = new Node(6);
        Node node2 = new Node(7);
        Node node3 = new Node(8);
        Node node4 = new Node(4);
        node.next=node1;
        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        System.out.println("排序前的链表为");
        Node help =node;
        while (help!=null){
            System.out.println(help);
            help=help.next;
        }

        Node process = process(node);

        System.out.println("排序后的链表为");
        while (process!=null){
            System.out.println(process);
            process=process.next;
        }
    }

    public static Node process(Node head){
        if (head==null||head.next==null){
            return head;
        }
        //找到中点 以及下一个链表的头节点
        Node midNode = T4.getTheMidNode(head);
        Node nextHead=midNode.next;
        //拆分链表---不要遗忘
        midNode.next=null;
        //排序
        return mergeSort(process(head),process(nextHead));
    }

    //两个有序链表合并
    private static Node mergeSort(Node a, Node b) {
        Node help, other;
        help=new Node(0);
        other=help;
        //依次往后遍历  排序
        while (a!=null&&b!=null){
            if (a.value<b.value){
                other.next=a;
                a=a.next;
            }else{
                other.next=b;
                b=b.next;
            }
            other=other.next;
        }
        //当有其中一个链表排序完成之后，  辅助链表直接指向不为空的链表
        other.next= a==null? b :a;

        return help.next;
    }

}
